package com.squirrel.michale;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/8 6:46 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2530 {


    public long maxKelements(int[] nums, int k) {
        MyMaxHeap my = new MyMaxHeap(nums.length);
        for (int i = 0; i < nums.length; i++) {
             if (!my.isFull()) {
                 my.push(nums[i]);
            }
        }
        long sum = 0;
        for (int i = 0; i < k; i++) {
            int element = my.pop();
            sum += element;
            int newEle = (element + 2) / 3;
            my.push(newEle);
        }
        return sum;
        // 时间复杂度 klogn
    }


    public long maxKelements2(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for (int i = 0; i < nums.length; i++) {
                heap.add(nums[i]);
        }
        long sum = 0;
        for (int i = 0; i < k; i++) {
            int element = heap.poll();
            sum += element;
            int newEle = (element + 2) / 3;
            heap.add(newEle);
        }
        return sum;
        // 时间复杂度 klogn
    }


    public static void main(String[] args) {

        LeetCode2530 leetCode2530 = new LeetCode2530();

        int[] nums = new int[]{10,10,10,10,10};
        int k = 5;
        System.out.println(leetCode2530.maxKelements(nums, k));
        System.out.println(leetCode2530.maxKelements2(nums, k));


        int[] nums2 = new int[]{1,10,3,3,3};
        int k2= 3;
        System.out.println(leetCode2530.maxKelements(nums2, k2));
        System.out.println(leetCode2530.maxKelements2(nums2, k2));

    }


}
